#pragma once
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <assert.h>
//哈希捅实现哈希表
using namespace std;
namespace cc
{
	//哈希捅的每个节点
	template<class K,class V>
	struct hashnode
	{
		pair<K, V> _val;
		hashnode<K, V>* _next = nullptr;
		hashnode(const pair<K,V>& x)
			:_val(x)
		{}
	};
	//哈希表
	template<class K, class V>
	class hash
	{
	public:
		typedef hashnode<K, V> node;
		hash()
		{}
		hash(const hash<K, V>& h)
		{
			_table.resize(h._table.size(), nullptr);
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (h._table[i] != nullptr)
				{
					node* cur = h._table[i];
					while (cur)
					{
						node* copy = new node(cur->_val);
						copy->_next = _table[i];
						_table[i] = copy;
						cur = cur->_next;
					}
				}
			}
			_size = h._size;
		}
		bool insert(const pair<K, V>& x)
		{
			//如果需要扩容或是此时是一个空表
			//注意：这里其实有个负荷因子，因为STL中的用哈希桶实现的哈希表中，负荷因子的大小是1，所以就是相等，如果用线性探测或是二次探测
			//的方法，就不能控制在1，最好控制在0.7-0.8左右就开始扩容,扩容其实根据专业人士的研究，扩容的大小最好是质数的，出现哈希碰撞的几率
			//就比较少
			if (_size == _table.size())
			{
				vector<node*> tem;
				tem.resize(_table.size() == 0 ? 10 : _table.size() * 2, nullptr);
				//旧表节点移动到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					node* cur = _table[i];
					while (cur)
					{
						cur->_next = tem[i];
						tem[i] = cur;
						cur = cur->_next;
					}
				}
				//移动完成，交换两个表
				tem.swap(_table);
			}
			node* newnode = new node(x);
			int ret = newnode->_val.first % _table.size();
			//头插
			newnode->_next = _table[ret];
			_table[ret] = newnode;
			_size++;
			return true;
		}
		node* find(const K& key)
		{
			int ret = key % _table.size();
			node* prev = nullptr;
			node* cur = _table[ret];
			while (cur)
			{
				if (cur->_val.first == key)
					return cur;
				prev = cur;
				cur = cur->_next;
			}
			return nullptr;
		}
		bool erase(const K& key)
		{
			if (_size == 0)
			{
				cout << "无法删除空表的内容" << endl;
				return false;
			}
			int ret = key % _table.size();
			node* prev = nullptr;
			node* cur = _table[ret];
			while (cur)
			{
				if (cur->_val.first == key)
				{
					if (prev)
						prev->_next = cur->_next;
					else
						_table[ret] = cur->_next;
					delete cur;
					_size--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}
	private:
		size_t _size = 0;
		vector<node*> _table;
	};
}



